# -*- coding: utf-8 -*-
# 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

# '?' 可以匹配任何单个字符。
# '*' 可以匹配任意字符串（包括空字符串）。
# 两个字符串完全匹配才算匹配成功。

# 说明:
# s 可能为空，且只包含从 a-z 的小写字母。
# p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

# 示例 1:
# 输入:
# s = "aa"
# p = "a"
# 输出: false
# 解释: "a" 无法匹配 "aa" 整个字符串。

# 示例 2:
# 输入:
# s = "aa"
# p = "*"
# 输出: true
# 解释: '*' 可以匹配任意字符串。

# 示例 3:
# 输入:
# s = "cb"
# p = "?a"
# 输出: false
# 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

# 示例 4:
# 输入:
# s = "adceb"
# p = "*a*b"
# 输出: true
# 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

# 示例 5:
# 输入:
# s = "acdcb"
# p = "a*c?b"
# 输入: false

# # 应该是解题成功，但是当前响应为超出时间限制
# 时间复杂度: 2的m次幂
# 
# class Solution(object):
#     def isMatch(self, s, p):
#         """
#         :type s: str
#         :type p: str
#         :rtype: bool
#         """
#         if(len(s)==0):
#             return len(p)==0 or p=="*" * len(p);
#         if(len(p)==0):
#             return len(s)==0;

#         is_match = p[0] in [s[0], "?"];
#         if p[0] == "*":
#             return self.isMatch(s[1:], p) or self.isMatch(s, p[1:]);
#         else:
#             return is_match and self.isMatch(s[1:], p[1:]);




# # 尝试使用动态规划的方法解决问题
# # 和0010相似，具体分析可以到0010查看
# 时间复杂度: m * n
# 
# class Solution(object):
#     def isMatch(self, s, p):
#         """
#         :type s: str
#         :type p: str
#         :rtype: bool
#         """
#         length_s = len(s);
#         length_p = len(p);

#         dp = [ [False] * (length_p + 1) for i in xrange(0, length_s + 1) ];
#         dp[0][0] = True;

#         for i in xrange(0, length_s + 1):
#             for j in xrange(1, length_p + 1):
#                 if p[j - 1] != "*":
#                     dp[i][j] = i >= 1 and j >= 1 and dp[i - 1][j - 1] and p[j - 1] in [ s[i - 1], "?" ];
#                 else:
#                     dp[i][j] = dp[i - 1][j] or dp[i][j - 1];

#         return dp[length_s][length_p];





# 查看解题思路尝试使用双指针进行解题
# 解题思路：
# 使用i,j分别指向s,p进行依次比对，分一下几种情况
# 1: 当p[j] != "*"时，属于正常的字符串匹配，如果s[i]和p[j]匹配，可以向前步进一步
# 2: 当p[j] == "*"时，记录下此时i,j的状态，并且让 j += 1，然后返回到 #1 的情况去匹配
#       解释相当于此时"*"完全没有发挥作用1个字符也没有匹配到
# 3: 以上2中情况都被归结为 #1 的情况进行处理，如果 #1 没有匹配成功怎么处理呢？分一下2中情况
#       a: 如果此时没有记忆"*"出现的状态，则可以返回False
#       b: 如果有记忆"*"出现的状态，则我们可以恢复到星星出现的位置，让"*"多匹配一个字符，然后再进行匹配
# 
# 综上在有"*"存在的情况下，算法尝试了"*"匹配到0,1,2,3,4...个字符的所有情况，所以算法是把所有情况都考虑到内的
# 
# 注意：
#   这里需要注意到，算法只记忆了一次"*"的状态，所以如果多次出现"*"，那么后出现的会把之前出现的"*"的状态覆盖掉
#   
#   然而这并不对算法的正确性造成影响，例子如下:
#   eg: "ababrghjkkuacdlm" "a*a*lm"
#   第二个"*"的状态覆盖掉了第一个"*"的状态，然而我们可以看到
#   "a*"可以匹配到"ab", "ababrghjkku"
#   "a*a*"可以匹配到"ababrghjkkuacd"
#   无论第一个"*"的状态如何我们都可以通过扩展第二个"*"来达到第一个"*"的效果
#   
# 时间复杂度: 最大为m * n
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        i = 0;
        j = 0;
        p_star_position = -1;
        s_star_position = -1;

        while i < len(s):
            if j < len(p) and p[j] in [ s[i], "?" ]:
                i += 1;
                j += 1;
            elif j < len(p) and p[j] == "*":
                s_star_position = i;
                p_star_position = j;
                j += 1;
            elif p_star_position != -1:
                s_star_position += 1;
                i = s_star_position;
                j = p_star_position + 1;
            else:
                return False;

        if j == len(p) and i == len(s):
            return True;

        return p[j:] == "*" * (len(p) - j);



t = Solution();

t_list = [];

t_list.append(["", "a", False]);
t_list.append(["aa", "a", False]);
t_list.append(["aa", "*", True]);
t_list.append(["cb", "*a", False]);
t_list.append(["adceb", "a*b", True]);
t_list.append(["acdcb", "a*c?b", False]);
t_list.append(["", "*", True]);
t_list.append(["", "", True]);
t_list.append(["ho", "ho**", True]);
t_list.append(["aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab", "*ab***ba**b*b*aaab*b", True]);
t_list.append(["aab", "c*a*b", False]);

for t_v in t_list:
    if t.isMatch(t_v[0], t_v[1]) != t_v[2]:
        print u"失败";
        print t_v;
        break;
    else:
        print ".";